

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>


<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<base target="_top">
<style type="text/css">
  

/* default css */

table {
  font-size: 1em;
  line-height: inherit;
  border-collapse: collapse;
}


tr {
  
  text-align: left;
  
}


div, address, ol, ul, li, option, select {
  margin-top: 0px;
  margin-bottom: 0px;
}

p {
  margin: 0px;
}


pre {
  font-family: Courier New;
  white-space: pre-wrap;
  margin:0;
}

body {
  margin: 6px;
  padding: 0px;
  font-family: Verdana, sans-serif;
  font-size: 10pt;
  background-color: #ffffff;
  color: #000;
}


img {
  -moz-force-broken-image-icon: 1;
}

@media screen {
  html.pageview {
    background-color: #f3f3f3 !important;
    overflow-x: hidden;
    overflow-y: scroll;
  }

  

  body {
    min-height: 1100px;
    
    counter-reset: __goog_page__;
  }
  
  * html body {
    height: 1100px;
  }
  /* Prevent repaint errors when scrolling in Safari. This "Star-7" css hack
     targets Safari 3.1, but not WebKit nightlies and presumably Safari 4.
     That's OK because this bug is fixed in WebKit nightlies/Safari 4 :-). */
  html*#wys_frame::before {
    content: '\A0';
    position: fixed;
    overflow: hidden;
    width: 0;
    height: 0;
    top: 0;
    left: 0;
  }
  
  .pageview body {
    border-top: 1px solid #ccc;
    border-left: 1px solid #ccc;
    border-right: 2px solid #bbb;
    border-bottom: 2px solid #bbb;
    width: 648px !important;
    margin: 15px auto 25px;
    padding: 40px 50px;
  }
  /* IE6 */
  * html {
    overflow-y: scroll;
  }
  * html.pageview body {
    overflow-x: auto;
  }
  

  
    
    .writely-callout-data {
      display: none;
    }
    

    .writely-footnote-marker {
      background-image: url('MISSING');
      background-color: transparent;
      background-repeat: no-repeat;
      width: 7px;
      overflow: hidden;
      height: 16px;
      vertical-align: top;

      
      -moz-user-select: none;
    }
    .editor .writely-footnote-marker {
      cursor: move;
    }
    .writely-footnote-marker-highlight {
      background-position: -15px 0;
      -moz-user-select: text;
    }
    .writely-footnote-hide-selection ::-moz-selection, .writely-footnote-hide-selection::-moz-selection {
      background: transparent;
    }
    .writely-footnote-hide-selection ::selection, .writely-footnote-hide-selection::selection {
      background: transparent;
    }
    .writely-footnote-hide-selection {
      cursor: move;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }

  


  
  .br_fix span+br:not(:-moz-last-node) {
    
    position:relative;
    
    left: -1ex
    
  }

  
  #cb-p-tgt {
    font-size: 8pt;
    padding: .4em;
    background-color: #ddd;
    color: #333;
  }
  #cb-p-tgt-can {
    text-decoration: underline;
    color: #36c;
    font-weight: bold;
    margin-left: 2em;
  }
  #cb-p-tgt .spin {
    width: 16px;
    height: 16px;
    background: url(//ssl.gstatic.com/docs/clipboard/spin_16o.gif) no-repeat;
  }
}

h6 { font-size: 8pt }
h5 { font-size: 8pt }
h4 { font-size: 10pt }
h3 { font-size: 12pt }
h2 { font-size: 14pt }
h1 { font-size: 18pt }

blockquote {padding: 10px; border: 1px #DDD dashed }

.webkit-indent-blockquote { border: none; }

a img {border: 0}

.pb {
  border-width: 0;
  page-break-after: always;
  /* We don't want this to be resizeable, so enforce a width and height
     using !important */
  height: 1px !important;
  width: 100% !important;
}

.editor .pb {
  border-top: 1px dashed #C0C0C0;
  border-bottom: 1px dashed #C0C0C0;
}

div.google_header, div.google_footer {
  position: relative;
  margin-top: 1em;
  margin-bottom: 1em;
}


/* Table of contents */
.editor div.writely-toc {
  background-color: #f3f3f3;
  border: 1px solid #ccc;
}
.writely-toc > ol {
  padding-left: 3em;
  font-weight: bold;
}
ol.writely-toc-subheading {
  padding-left: 1em;
  font-weight: normal;
}
/* IE6 only */
* html writely-toc ol {
  list-style-position: inside;
}
.writely-toc-none {
  list-style-type: none;
}
.writely-toc-decimal {
  list-style-type: decimal;
}
.writely-toc-upper-alpha {
  list-style-type: upper-alpha;
}
.writely-toc-lower-alpha {
  list-style-type: lower-alpha;
}
.writely-toc-upper-roman {
  list-style-type: upper-roman;
}
.writely-toc-lower-roman {
  list-style-type: lower-roman;
}
.writely-toc-disc {
  list-style-type: disc;
}

/* Ordered lists converted to numbered lists can preserve ordered types, and
   vice versa. This is confusing, so disallow it */
ul[type="i"], ul[type="I"], ul[type="1"], ul[type="a"], ul[type="A"] {
  list-style-type: disc;
}

ol[type="disc"], ol[type="circle"], ol[type="square"] {
  list-style-type: decimal;
}

/* end default css */


  /* default print css */
  @media print {
    body {
      padding: 0;
      margin: 0;
    }

    div.google_header, div.google_footer {
      display: block;
      min-height: 0;
      border: none;
    }

    div.google_header {
      flow: static(header);
    }

    /* used to insert page numbers */
    div.google_header::before, div.google_footer::before {
      position: absolute;
      top: 0;
    }

    div.google_footer {
      flow: static(footer);
    }

    /* always consider this element at the start of the doc */
    div#google_footer {
      flow: static(footer, start);
    }

    span.google_pagenumber {
      content: counter(page);
    }

    span.google_pagecount {
      content: counter(pages);
    }

    .endnotes {
      page: endnote;
    }

    /* MLA specifies that endnotes title should be 1" margin from the top of the page. */
    @page endnote {
      margin-top: 1in;
    }

    callout.google_footnote {
      
      display: prince-footnote;
      footnote-style-position: inside;
      /* These styles keep the footnote from taking on the style of the text
         surrounding the footnote marker. They can be overridden in the
         document CSS. */
      color: #000;
      font-family: Verdana;
      font-size: 10.0pt;
      font-weight: normal;
    }

    /* Table of contents */
    #WritelyTableOfContents a::after {
      content: leader('.') target-counter(attr(href), page);
    }

    #WritelyTableOfContents a {
      text-decoration: none;
      color: black;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }
  }

  @page {
    @top {
      content: flow(header);
    }
    @bottom {
      content: flow(footer);
    }
    @footnotes {
      border-top: solid black thin;
      padding-top: 8pt;
    }
  }
  /* end default print css */


/* custom css */


/* end custom css */

/* ui edited css */

body {
  font-family: Verdana;
  
  font-size: 10.0pt;
  line-height: normal;
  background-color: #ffffff;
}
/* end ui edited css */


/* editor CSS */
.editor a:visited {color: #551A8B}
.editor table.zeroBorder {border: 1px dotted gray}
.editor table.zeroBorder td {border: 1px dotted gray}
.editor table.zeroBorder th {border: 1px dotted gray}


.editor div.google_header, .editor div.google_footer {
  border: 2px #DDDDDD dashed;
  position: static;
  width: 100%;
  min-height: 2em;
}

.editor .misspell {background-color: yellow}

.editor .writely-comment {
  font-size: 9pt;
  line-height: 1.4;
  padding: 1px;
  border: 1px dashed #C0C0C0
}


/* end editor CSS */

</style>

  
  <title>W7 Elekcja, wzaajemne wykluczanie</title>

</head>

<body 
    
    >
    
    
    
<div id=lkrj style=TEXT-ALIGN:left>
  <b style=COLOR:#3d85c6><font size=5>Elekcja, wzajemne wykluczanie i zakleszczenie</font></b><br>
  <hr size=2>
  <p>
    <br>
    Wykład obejmuje wybrane zagadnienia z synchronizacji i jest kontynuacją poprzedniego wykładu, głównie zagadnień odnoszących się do synchronizacji zegarów fizycznych i logicznych, a także transakcji. Tematy poruszane w tym wykładzie są równie ważne i przydatne w kontekście synchronizacji w systemach rozproszonych.<br>
  </p>
  <p>
    <br>
  </p>
  <p>
    Wykład składa się z trzech głównych części. W pierwszej części zajmiemy się algorytmami elekcji, które są bardzo istotne z punktu widzenia systemów rozproszonych, ponieważ są wykorzystywane w ramach innych algorytmów. Następnie przejdziemy do problematyki wzajemnego wykluczania. W trzeciej i ostatniej części wykładu poruszymy temat zakleszczeń w systemach rozproszonych.
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Algorytmy elekcji</font></b><br>
  <hr size=2><br>
  <div id=duja style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2435f354n6gv_b.png" style=HEIGHT:340px;WIDTH:500px><br>
    <br>
    Algorytmy rozproszone wymagają często specjalnego procesu, który będzie <b>koordynatorem</b> działań innych procesów. Do wyboru koordynatora stosuje się tzw. <b>algorytmy</b> <b>elekcji</b> (ang. <i>election</i> <i>algorithms</i>).<br>
    <br>
    <p>
      Do ustalenia koordynatora niezbędna jest możliwość rozróżnienia procesów, które biorą udział w elekcji. W tym celu założymy, również na potrzeby prezentowanych algorytmów, że każdy proces ma przypisaną pewną unikalną liczbę, pewnego rodzaju identyfikator. Liczba taka pozwala w najprostszym przypadku znaleźć koordynatora np. poprzez wybór największej wartości liczbowej. Ponadto przyjmujemy, że każdy proces zna identyfikatory pozostałych procesów.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Prezentowane dalej algorytmy zasadniczo różnią się jedynie sposobem lokalizacji koordynatora. Poprawny algorytm elekcji powinien zapewnić, że jeżeli został wybrany proces-koordynator, to zgodziły się na to wszystkie inne procesy.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Algorytm tyrana</font></b><br>
    <hr size=2><br>
    <div id=xsqe style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2436d5qqd3cq_b.png" style=HEIGHT:340px;WIDTH:500px><br>
      <br>
      <b>Algorytm</b> <b>tyrana</b> (ang. <i>bully</i> <i>algorithm</i> ) jest pierwszym z dwóch algorytmów elekcji, które zaprezentujemy.<br>
      <br>
      <p>
        Kiedy proces zauważa, że koordynator nie odpowiada już na żądania, rozpoczyna elekcję.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Proces <i>P</i> wysyła wiadomość <i>ELEKCJA</i> do wszystkich procesów z wyższą liczbą. Jeżeli nikt nie odpowiada, <i>P</i> wygrywa elekcję i staje się koordynatorem. Jeżeli natomiast odpowie jeden z procesów o wyższej liczbie, to ten proces przejmuje zadanie.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        W dowolnym momencie proces może otrzymać wiadomość <i>ELEKCJA</i> od jednego z procesów o niższej liczbie. Kiedy taka wiadomość dotrze, odbiorca odsyła z powrotem do nadawcy wiadomość potwierdzającą, że działa i przejmuje kontrolę. Odbiorca podtrzymuje wtedy proces elekcji, jeżeli jej nie przeprowadzał do tej pory.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        W końcu wszystkie procesy za wyjątkiem jednego zaprzestają elekcji i właśnie ten jedyny proces staje się koordynatorem. Ogłasza on następnie swoje zwycięstwo poprzez rozesłanie do wszystkich procesów wiadomości z informacją, że jest nowym koordynatorem.
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Algorytm tyrana - przykład</font></b><br>
      <hr size=2><br>
      <div id=vagf style=TEXT-ALIGN:left>
        <div id=o.-o style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2442gtkhrpdt_b.jpg" style=HEIGHT:359.833px;WIDTH:500px>
        </div>
      </div>
      <br>
      Na powyższej ilustracji znajduje się przykład wykonania algorytmu elekcji dla 8 procesów. Procesy oznaczone są kolejno numerami od 1 do 8.<br>
      <br>
      <p>
        Proces 8., który był do tej pory koordynatorem ulega awarii. Zauważył to proces 5., który rozpoczyna w tym momencie algorytm elekcji. Robi to rozsyłając do procesów o wyższych numerach (6, 7, 8) wiadomość <i>ELEKCJA</i> . Te odsyłają mu <i>ODPOWIEDŹ</i> , w celu powiadomienia go, że przejmują kontrolę nad algorytmem elekcji (za wyjątkiem 8., który nie działa). Następnie proces 6. i 7. wysyłają zapytanie do procesów o wyższych od siebie numerach. W ten sposób proces 7. nie otrzymuje żadnej odpowiedzi i zostaje koordynatorem, o czym informuje pozostałe procesy rozsyłając wiadomość <i>KOORDYNATOR</i> .
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Algorytm pierścieniowy</font></b><br>
      <hr size=2><br>
    </div>
    <div id=p33v style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2437dsghmpfv_b.png" style=HEIGHT:341px;WIDTH:500px><br>
      <br>
      Kolejnym prezentowanym algorytmem elekcji jest algorytm pierścieniowy.<br>
      <br>
      <p>
        Algorytm używa pierścienia, ale bez żetonu, który często występuje w algorytmach tego typu.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Gdy jakiś proces zauważy, że koordynator nie funkcjonuje, konstruuje wiadomość <i>ELEKCJA</i> zawierającą jego własny numer i wysyła ją do swojego następcy. Ten z kolei dodaje do listy w otrzymanej wiadomości swój numer i wysyła do swojego następcy itd. Dodanie numeru przez proces oznacza, że bierze on udział w wyborach, jako jeden z kandydatów na koordynatora.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Ostatecznie wiadomość dociera z powrotem do procesu który ją zapoczątkował. Typ wiadomości jest zmieniany na <i>KOORDYNATOR</i> i wiadomość puszczana jest w obieg jeszcze raz. Tym razem jednak w celu powiadomienia wszystkich procesów, kto jest koordynatorem (proces na liście o największym numerze).
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Algorytm pierścieniowy - przykład</font></b><br>
      <hr size=2><br>
      <div id=sdi6 style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2439dcrzcjhr_b.png" style=HEIGHT:341px;WIDTH:500px>
      </div>
      <br>
      Prześledzimy teraz wykonanie pierścieniowego algorytmu elekcji dla 8 procesów. Załóżmy, że proces 8. był koordynatorem i uległ nagle awarii. Zauważył to proces 5., który rozpoczyna algorytm elekcji i wysyła wiadomość <i>ELEKCJA</i> <i>,</i> z dołączonym swoim numerem, do następnego procesu w pierścieniu. Proces, który odbierze wiadomość elekcja dołącza swój numer i przesyła dalej wiadomość do sąsiedniego procesu w pierścieniu. Wiadomość <i>ELEKCJA</i> jest przesyłana do momentu, aż nie dotrze do procesu 5. Ten oblicza ze wszystkich otrzymanych numerów największy dostępny i wysyła wiadomość <i>KOORDYNATOR</i> , która okrąża pierścień i powiadamia pozostałe procesy, że proces 7. zostaje nowym koordynatorem.<br>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Wzajemne wykluczanie</font></b><br>
      <hr size=2>
    </div>
    <br>
  </div>
  <div id=pfds style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2440cffw7fgw_b.png" style=HEIGHT:340px;WIDTH:500px>
  </div>
  <br>
  Kolejnym problemem jakim się zajmiemy jest wzajemne wykluczanie. Temat wzajemnego wykluczania wywodzi się ze sposobu programowania systemów z wieloma procesami. Do tego celu wykorzystuje się sekcje krytyczne, które na czas wykonywania operacji na pewnych zasobach, zapewniają procesom wzajemne wykluczanie. Gdy proces wchodzi do sekcji krytycznej, może mieć pewność, że jakiś inny proces nie wejdzie do niej w tym samym czasie.
  <p>
    <br>
  </p>
  <p>
    Wzajemne wykluczanie jest ważne także w systemach jednoprocesorowych, jednakże dalej zajmiemy się algorytmami, które są częściej stosowane w systemach rozproszonych.
  </p>
  <br>
  <br>
  <b style=COLOR:#3d85c6><font size=3>Podejście scentralizowane</font></b><br>
  <hr size=2><br>
  <div id=tjxp style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2441drfvfwg8_b.png" style=HEIGHT:342px;WIDTH:500px><br>
    <br>
    Spośród dostępnych procesów jeden wybierany jest jako koordynator. Kiedykolwiek proces chce wejść do sekcji krytycznej wysyła informację z żądaniem do koordynatora, określając do której sekcji krytycznej chce wejść i pytając zarazem o pozwolenie. Jeżeli w danej chwili żaden z procesów nie jest w tej sekcji krytycznej, koordynator odsyła odpowiedź udzielającą pozwolenia. Kiedy odpowiedź dotrze, proces, który ubiegał się o wejście do sekcji krytycznej, uruchamia ją. Natomiast gdy inny proces zapyta o pozwolenie na wejście do tej samej sekcji krytycznej, koordynator po prostu wstrzymuje się z odpowiedzią, blokując w ten sposób proces, który czeka na odpowiedź. Ewentualnie może np. odesłać odpowiedź z odmową wejścia do sekcji krytycznej.<br>
    <br>
    <p>
      Algorytm ten posiada kilka istotnych własności.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Jest sprawiedliwy w tym sensie, że procesy są obsługiwane są zgodnie z kolejnością żądań. Dodatkowo każdy z procesów w końcu, będzie mógł uruchomić swoją sekcję krytyczną. Innymi słowy algorytm nie powoduje zagłodzenia. Jest prosty w implementacji. Proces wejścia do sekcji krytycznej wymaga tylko trzech wiadomości.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Wadą algorytmu jest scentralizowany koordynator, który może ulec awarii.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Podejście scentralizowane - przykład</font></b><br>
    <hr size=2>
  </div>
  <br>
  <div id=wi_o style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2443cct7wfcr_b.jpg" style=HEIGHT:356.164px;WIDTH:500px><br>
    <br>
    Niech <i>proces</i> <i>Pc</i> będzie koordynatorem, który kontroluje sekcje krytyczne. Załóżmy, że <i>proces</i> <i>P1</i> chce wejść do sekcji krytycznej i wysyła żądanie do <i>Pc</i> . Ponieważ w danej sekcji krytycznej nikogo aktualnie nie ma, <i>Pc</i> odsyła odpowiedź z pozwoleniem na wejście do sekcji krytycznej do <i>P1</i> . Następnie okazuje się, że procesy <i>P2</i> <i>i</i> <i>P3</i> również zgłaszają zapotrzebowanie na sekcję krytyczną, która jest aktualnie zajęta przez <i>P1</i> . W związku z tym <i>P2</i> <i>i</i> <i>P3</i> zostają umieszczone w kolejce do późniejszego rozpatrzenia po zwolnieniu sekcji krytycznej przez <i>P1</i> . Gdy <i>P1</i> zakończyło wykonywanie sekcji krytycznej odsyła do <i>Pc</i> wiadomość zwalniającą, po czym <i>Pc</i> odsyła pozwolenie kolejnemu procesowi w kolejce oczekujących na sekcje krytyczną (proces <i>P2</i> ). Po zwolnieniu sekcji przez <i>P2</i> , dostęp do niej uzyskuje <i>P3</i> .<br>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Algorytm Lamporta - wprowadzenie</font></b><br>
    <hr size=2>
  </div>
  <br>
  <div id=ha8u style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2444hjzmvrhx_b.png" style=HEIGHT:340px;WIDTH:500px><br>
    <br>
    <p>
      Lamport był pierwszym, który podał rozproszony algorytm wzajemnego wykluczania, jako przykład zastosowania wymyślonego przez siebie schematu synchronizacji zegarów.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Jako <i>Ri</i> oznaczmy <i>zbiór</i> <i>żądań</i> (ang. <i>request</i> <i>set</i> ) procesu <i>Pi</i> , tzn. zbiór procesów, od których <i>Pi</i> wymaga pozwolenia, kiedy chce się dostać do sekcji krytycznej. W algorytmie Lamporta zbiór żądań każdego procesu jest zbiorem wszystkich innych procesów. Każdy proces <i>Pi</i> utrzymuje kolejkę <i>kolejka_żądań(i</i> <i>),</i> która zawiera żądania wejścia do sekcji krytycznej uszeregowane według ich znaczników czasowych. Algorytm ten wymaga, aby wiadomości dostarczane były pomiędzy każdą parą procesów w kolejności FIFO (ang. <i>First</i> <i>In</i> <i>,</i> <i>First</i> <i>Out</i> – pierwszy na wejściu, pierwszy na wyjściu).
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Algorytm Lamporta</font></b><br>
    <hr size=2><br>
  </div>
  <div id=ujpj style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2445gtrb32f5_b.png" style=HEIGHT:340px;WIDTH:500px><br>
    <br>
    Gdy proces <i>Pi</i> zamierza wejść do sekcji krytycznej, wysyła wiadomość z żądaniem do wszystkich procesów, które znajdują się wewnątrz jego zbioru żądań <i>Ri</i> . Następnie umieszcza żądanie w swojej kolejce żądań (<i>ts(i</i> <i>)</i> jest znacznikiem czasowym żądania procesu <i>Pi</i> ). Gdy proces <i>Pj</i> otrzyma żądanie od procesu <i>Pi</i> , odsyła <i>ODPOWIEDŹ</i> oznaczoną znacznikiem czasowym do procesu <i>Pi</i> i umieszcza żądanie procesu <i>Pi</i> w swojej kolejce żądań. Proces <i>Pi</i> rozpoczyna wykonywanie sekcji krytycznej, gdy spełnione są dwa następujące warunki: 1) proces <i>Pi</i> otrzymał wiadomość ze znacznikiem czasowym większym niż <i>(</i> <i>ts(i</i> <i>),</i> <i>i</i> <i>)</i> od wszystkich innych procesów oraz 2) żądanie procesu <i>Pi</i> jest na początku jego własnej kolejki żądań<br>
    <br>
    <p>
      Po wyjściu z sekcji krytycznej proces <i>Pi</i> usuwa żądanie ze swojej kolejki żądań i wysyła wiadomości <i>ZWOLNIJ</i> oznaczoną znacznikiem czasowym do wszystkich procesów, znajdujących się w jego zbiorze żądań. Jeżeli proces <i>Pj</i> otrzyma wiadomość zwolnij od procesu <i>Pi</i> , usuwa żądanie <i>Pi</i> ze swojej kolejki żądań.<br>
    </p>
    <p>
      <br>
    </p>
    <p>
      Kiedy proces usuwa pewne żądanie ze swojej kolejki żądań, jego własne żądanie może pojawić się na początku kolejki, umożliwiając mu wejście do sekcji krytycznej. Algorytm wykonuje żądania wejścia do sekcji krytycznej w rosnącym porządku i zgodnie z ich znacznikami czasowymi.
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Algorytm Lamporta - przykład</font></b><br>
    <hr size=2><br>
  </div>
  <div id=fcb2 style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2446cg9w4ffs_b.png" style=HEIGHT:342px;WIDTH:500px><br>
    <br>
    Prześledzimy teraz działanie algorytmu Lamporta na przykładzie 3 procesów. Proces <i>P2</i> chce wykonać sekcję krytyczną i wysyła żądanie oznaczone znacznikiem czasu (1, 2) do procesów <i>P1</i> oraz <i>P2</i> . W międzyczasie do sekcji krytycznej chce wejść również proces <i>P1</i> i również wysyła żądania ze znacznikiem (2, 1) do pozostałych procesów <i>P2</i> oraz <i>P3</i> . Odpowiednie procesy odsyłają odpowiedzi opatrzone znacznikami czasowymi tzn. <i>P1</i> i <i>P3</i> do <i>P2</i> , a <i>P2</i> i <i>P3</i> do <i>P1</i> . W tym momencie procesy <i>P1</i> <i>i</i> <i>P2</i> otrzymały wszystkie niezbędne odpowiedzi, ale to proces <i>P2</i> otrzymuje pozwolenie na wejście do sekcji krytycznej, ponieważ znacznik czasu jego żądania jest najmniejszy, a samo żądanie znalazło się na początku kolejki. Po wyjściu z sekcji krytycznej <i>P2</i> wysyła wiadomość zwalniającą do <i>P1</i> oraz <i>P3</i> . Po otrzymaniu tej wiadomości żądanie <i>P1</i> znajduje się na szczycie jego kolejki i <i>P1</i> może wejść do sekcji krytycznej.<br>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Algorytm Ricarta i Agrawali</font></b><br>
    <hr size=2><br>
    <div id=k-yw style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2447d2vd78d4_b.png" style=HEIGHT:342px;WIDTH:500px><br>
      <br>
      Algorytm Ricarta i Agrawali jest zoptymalizowana wersją algorytmu Lamporta, która obywa się bez wiadomości <i>ZWOLNIJ</i> (sekcję krytyczną) poprzez sprytne połączenie ich z wiadomościami typu <i>ODPOWIEDŹ</i>.<br>
      <br>
      <p>
        Gdy proces <i>Pi</i> chce wejść do sekcji krytycznej, wysyła wiadomość z żądaniem oznaczoną znacznikiem czasowym do wszystkich procesów, które znajdują się w jego zbiorze żądań. W momencie gdy proces <i>Pj</i> otrzyma żądanie od procesu <i>Pi</i> , wysyła odpowiedź do procesu <i>Pi</i> pod warunkiem, że nie zachodzi jedna z następujących sytuacji: 1) proces <i>Pj</i> wykonuje sekcję krytyczną, 2) proces <i>Pj</i> żąda wykonania sekcji krytycznej, a znacznik czasowy jego żądania jest mniejszy niż znacznik czasowy żądania procesu <i>Pi</i> . Jeżeli zachodzi, któraś z tych dwóch sytuacji, żądanie procesu <i>Pi</i> jest odkładane i trafia do kolejki żądań w procesie <i>Pj</i>.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Proces <i>Pi</i> wchodzi do sekcji krytycznej po otrzymaniu wiadomości <i>ODPOWIEDŹ</i> od wszystkich procesów, które są w jego zbiorze <i>Ri</i> . W chwili kiedy proces <i>Pi</i> kończy wykonywanie sekcji krytycznej wysyła odpowiedzi na wszystkie odłożone wcześniej żądania, a następnie usuwa je z kolejki.<br>
      </p>
      <p>
        <br>
      </p>
      <p>
        Odpowiedzi na żądania procesu blokowane są tylko przez procesy, które ubiegają się o wejście do sekcji krytycznej i mają wyższy priorytet tzn. mniejszy znacznik czasowy. W ten sposób, gdy proces odsyła wiadomość typu odpowiedź na wszystkie odroczone żądania, proces, który ma kolejny najwyższy priorytet żądania, otrzymuje ostatnią niezbędną odpowiedź i wchodzi do sekcji krytycznej. Innymi słowy sekcje krytyczne w algorytmie Ricarta i Agrawali wykonywane są w kolejności zgodnej z wartościami znaczników czasowych ich żądań.
      </p>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Algorytm Ricarta i Agrawali - przykład</font></b><br>
      <hr size=2><br>
    </div>
    <div id=ktt7 style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2448df8w2nfj_b.png" style=HEIGHT:341px;WIDTH:500px><br>
      <br>
      Rozpatrzmy przykład wykonania algorytmu Ricarta i Agrawali dla 3 procesów. Algorytm początkowo przebiega podobnie jak w przypadku przykłady dla algorytmu Lamporta. Dwa procesy <i>P1</i> oraz <i>P2</i> wysyłają żądania na wejście do sekcji krytycznej. <i>P3</i> odsyła odpowiedzi do <i>P1</i> i <i>P2</i> , <i>P1</i> odsyła odpowiedź do <i>P2</i> . W międzyczasie <i>P2</i> , otrzymało wszystkie niezbędne odpowiedzi i jego własne żądanie znalazło się z najmniejszym znacznikiem na szczycie lokalnej kolejki, wchodzi do sekcji krytycznej. Dopiero po wyjściu z sekcji krytycznej <i>P2</i> odsyła odpowiedź do <i>P1</i> , które może wtedy wejść do sekcji krytycznej.<br>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Algorytm Maekawy - wprowadzenie</font></b><br>
      <hr size=2><br>
      <div id=xhvk style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2449pk4tzj97_b.png" style=HEIGHT:340px;WIDTH:500px><br>
        <br>
        Algorytm Maekawy różni się od typowych algorytmów wzajemnego wykluczania. Świadczą o tym głównie dwie jego własności.<br>
        <br>
        <p>
          Po pierwsze proces, który chce wejść do sekcji krytycznej, nie żąda pozwolenia od wszystkich procesów, ale tylko od pewnego ich podzbioru. Jest to znacząco różne podejście w stosunku do algorytmu Lamporta i algorytmu Ricarta i Agrawali, gdzie wszystkie procesy uczestniczą w rozwiązywaniu konfliktu. W algorytmie Meakawy zbiory procesów, do których wysyłane są żądania, wybierane są w taki sposób, aby iloczyn dowolnych dwóch różnych zbiorów był zbiorem niepustym. W rezultacie tego każda para procesów, posiada proces, który pośredniczy między nimi w rozwiązywaniu ewentualnych konfliktów.
        </p>
        <p>
          <br>
        </p>
        <p>
          Po drugie w algorytmie Maekawy dowolny proces może wysłać naraz tylko jedną odpowiedź. Ponadto procesowi wolno wysłać odpowiedź tylko po otrzymaniu wiadomości typu <i>ZWOLNIJ</i> , która dotyczy poprzedniej wiadomości <i>ODPOWIEDŹ</i> . Z tego powodu proces <i>Pi</i> , zanim wejdzie do sekcji krytycznej, blokuje wszystkie pozostałe procesy, które razem z nim należą do pewnego podzbioru procesów oznaczonego przez <i>Ri</i> (zwanego dalej również podzbiorem żądań procesu <i>Pi</i> ).
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Konstrukcja zbioru żądań w alg. Maekawy</font></b><br>
        <hr size=2><br>
        <div id=v75_ style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2450dtf4gwdn_b.png" style=HEIGHT:342px;WIDTH:500px><br>
          <br>
          Konstrukcja zbioru żądań w algorytmie Maekawy wymaga, aby spełnionych było kilka warunków.<br>
          <br>
          <p>
            Ponieważ istnieje co najmniej jeden wspólny proces pomiędzy podzbiorami żądań dowolnych dwóch procesów (warunek <i>M1</i> ), każda para procesów posiada wspólny proces, który pośredniczy w rozwiązywaniu konfliktów pomiędzy nimi. W danej chwili proces może posiadać co najwyżej jedną zaległą wiadomość typu <i>ODPOWIEDŹ</i> . Oznacza to, że gdy przychodzi żądanie wejścia do sekcji krytycznej, proces udziela pozwolenia na jej wykonanie, jeżeli nie udzielił go wcześniej jakiemuś innemu procesowi. W ten sposób zapewnione jest wzajemne wykluczanie.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Warunki <i>M1</i> i <i>M2</i> są niezbędne dla poprawności, podczas gdy warunki <i>M3</i> i <i>M4</i> wprowadzają inne pożądane cechy algorytmu. Warunek <i>M3</i> określa równy rozmiar podzbiorów żądań wszystkich procesów. Oznacza to, że wszystkie procesy powinny wykonywać, równą ilość pracy, w celu wzajemnego wykluczania. Warunek <i>M4</i> wymusza, aby dokładanie ta sama liczba procesów żądała pozwolenia od dowolnego procesu. Innymi słowy wszystkie procesy ponoszą odpowiedzialność za udzielania pozwolenia innym procesom.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Algorytm Maekawy</font></b><br>
          <hr size=2><br>
          <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-7-wyk-2.0-Slajd15 title=Sr-7-wyk-2.0-Slajd15> </a>
          <div id=vufy style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2451fbdm6gds_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            W pierwszym kroku algorytmu wzajemnego wykluczania Maekawy proces <i>Pi</i> , który ubiega się o wejście do sekcji krytycznej, rozsyła <i>ŻĄDANIE(i</i> <i>)</i> do wszystkich procesów, od których wymaga pozwolenia (procesy ze zbioru żądań <i>Ri</i> procesu <i>Pi</i> ).<br>
            <br>
            <p>
              Kiedy proces <i>Pj</i> otrzyma komunikat <i>ŻĄDANIE(i</i> <i>),</i> wysyła <i>ODPOWIEDŹ(j</i> <i>)</i> do procesu <i>Pi</i> pod warunkiem, że nie wysłał już komunikatu z odpowiedzią od czasu otrzymania ostatniej wiadomości <i>ZWOLNIJ</i> . W przeciwnym wypadku komunikat z żądaniem trafia do kolejki, w celu jego późniejszego rozpatrzenia.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              W momencie kiedy proces <i>Pi</i> otrzyma komunikaty typu <i>ODPOWIEDŹ</i> od wszystkich procesów ze zbioru <i>Ri</i> , może uruchomić swoją sekcję krytyczną.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Po wykonaniu sekcji krytycznej, proces <i>Pi</i> wysyła wiadomości <i>ZWOLNIJ(i</i> <i>)</i> do wszystkich procesów w <i>Ri</i> . W wypadku kiedy proces <i>Pj</i> otrzyma komunikat <i>ZWOLNIJ(i</i> <i>)</i> od procesu <i>Pi</i> , wysyła <i>ODPOWIEDŹ</i> do następnego oczekującego procesu, który jest w jego kolejce i usuwa go z niej. Jeżeli kolejka jest pusta, wtedy proces aktualizuje swój stan, tak aby odzwierciedlał fakt, iż proces nie wysłał żadnego komunikatu <i>ODPOWIEDŹ</i>.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Algorytm Maekawy - przykład</font></b><br>
            <hr size=2>
          </div>
          <br>
        </div>
        <div id=nmbt style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2452fws2xh3k_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          Na ilustracji przedstawiono działanie algorytmu Maekawy dla 5 procesów. Mamy tu dwie grupy procesów: {<i>P1</i> , <i>P2</i> <i>,</i> <i>P3</i> } oraz {<i>P3</i> , <i>P4</i> , <i>P5</i> }. Wspólnym procesem dla obu zbiorów jest proces <i>P3</i>.<br>
          <br>
          <p>
            Proces <i>P1</i> żąda wejście do sekcji krytycznej i wysyła do wszystkich procesów {<i>P2</i> , <i>P3</i> } wewnątrz swojego zbioru żądań <i>ŻĄDANIE</i> . Procesy <i>P2</i> i <i>P3</i> , ponieważ nikomu wcześniej nie przydzieliły pozwolenia na wejście do sekcji krytycznej, odsyłają do <i>P1</i> pozwolenie na wejście do sekcji krytycznej (<i>ODPOWIEDŹ</i> ). <i>P1</i> wchodzi do sekcji krytycznej. W tym czasie do sekcji krytycznej chce się również dostać proces <i>P5</i> <i>i</i> <i>wysyła</i> <i>ŻĄDANIE</i> do procesów ze swojego zbioru żądań {<i>P3</i> , <i>P4</i> }. Ponieważ <i>P3</i> przydzieliło wcześniej już pozwolenie na wejście do sekcji krytycznej <i>P1</i> , w danym momencie nie może odesłać odpowiedzi do <i>P5</i> . Natomiast <i>P4</i> wysyła odpowiedź do <i>P5</i>.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Po zakończeniu sekcji krytycznej <i>P1</i> , wysyła wiadomość <i>ZWOLNIJ</i> do procesów <i>P2</i> oraz <i>P3</i> . <i>P3</i> <i>z</i> kolei może już odesłać odpowiedź do <i>P5</i>. <i>P5</i> wchodzi do sekcji krytycznej.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Algorytm Suzuki-Kasami - wprowadzenie</font></b><br>
          <hr size=2>
        </div>
        <br>
      </div>
      <div id=gjpi style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2453g3dfbzgx_b.png" style=HEIGHT:342px;WIDTH:500px><br>
        <br>
        W algorytmie, który zaproponowali Suzuki i Kasami, jeżeli proces próbuje się dostać do sekcji krytycznej i nie ma żetonu, rozsyła wiadomość z żądaniem o żeton do wszystkich inny procesów. Proces, który posiada żeton, wysyła go do procesu, który go żądał po otrzymaniu wiadomości <i>ŻĄDANIE</i> . Jeżeli proces otrzyma wiadomość z żądaniem w trakcie wykonywania sekcji krytycznej, wysyła żeton chwilę po tym jak wyjdzie z sekcji krytycznej. Proces, który posiada żeton może wchodzić do sekcji krytycznej dopóty dopóki nie odeśle żetonu innemu procesowi.
        <p>
          <br>
        </p>
        <p>
          Głównymi problemami projektowymi w tym algorytmie są: rozróżnianie przedawnionych żądań od bieżących oraz określenie, który proces ma zaległe żądanie sekcji krytycznej.
        </p>
        <br>
        <br>
        <div id=xris style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2454cs29v9gk_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          Przedawnione żądania są rozróżniane od bieżących w następujący sposób. Wiadomość <i>typu</i> <i>ŻĄDANIE</i> procesu <i>Pj</i> ma postać <i>ŻĄDANIE(j</i> <i>,</i> <i>n</i> <i>),</i> gdzie <i>n</i> <i>=</i> <i>1,2</i> <i>,…</i> jest liczbą porządkową, która wskazuje, że proces <i>Pj</i> żąda <i>n-tego</i> wykonania sekcji krytycznej. Proces <i>Pi</i> przechowuje tablicę liczb całkowitych <i>RNi[1</i> <i>..</i> <i>N</i> <i>],</i> gdzie <i>RNi[j</i> <i>]</i> jest największą liczbą porządkową otrzymaną do tej pory w żądaniu od procesu <i>Pj</i> . <i>ŻĄDANIE(j</i> <i>,</i> <i>n</i> <i>)</i> otrzymane przez proces <i>Pi</i> jest przedawnione jeżeli <i>RNi[j</i> <i>]&gt;</i> <i>n</i> . Kiedy proces <i>Pi</i> otrzymuje <i>ŻĄDANIE(j</i> <i>,</i> <i>n</i> <i>),</i> to zmienia <i>RNi[j</i> <i>]:=</i> <i>max(RNi[j</i> <i>],</i> <i>n</i> <i>).</i><br>
          <br>
          <br>
          <div id=cufi style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2455f5gx34g9_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            Procesy z zaległymi żądaniami sekcji krytycznej są określane przy użyciu zawartości żetonu. Żeton składa się z <b>kolejki</b> <b>żetonu</b> <i>Q</i> oraz <b>tablicy</b> <b>żetonu</b> <i>LN</i> , gdzie <i>Q</i> jest kolejką procesów żądających, natomiast <i>LN</i> jest tablicą o rozmiarze <i>N</i> , taką że <i>LN[j</i> <i>]</i> jest liczbą porządkową żądania, które proces <i>Pj</i> wykonał jako ostatnie. Po wykonaniu swojej sekcji krytycznej, proces <i>Pi</i> aktualizuje <i>LN[i</i> <i>]:=</i> <i>RNi[i</i> <i>],</i> aby wskazywało, że żądanie odpowiadające liczbie porządkowej <i>RNi[i</i> <i>]</i> zostało spełnione. Tablica żetonu <i>LN[1</i> <i>..</i> <i>N</i> <i>]</i> pozwala procesowi ustalić czy jakiś inny proces ma zaległe żądanie sekcji krytycznej. Zauważmy, że jeżeli dla procesu <i>Pi</i> mamy <i>RNi[j</i> <i>]=</i> <i>LN[j</i> <i>]+</i> <i>1</i> , wtedy proces <i>Pj</i> jest w stanie żądania żetonu. Po wykonaniu sekcji krytycznej, proces sprawdza ten warunek dla wszystkich wartości <i>j</i> , żeby określić wszystkie procesy, które żądają żetonu oraz umieszcza ich identyfikatory w kolejce <i>Q</i> , jeżeli do tej pory ich tam nie ma. Następnie proces ten wysyła żeton do procesu, który znajduje się na początku kolejki <i>Q</i> .<br>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Algorytm Suzuki-Kasami </font></b><br>
            <hr size=2><br>
            <div id=ysvy style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2456dsj3gjgg_b.png" style=HEIGHT:341px;WIDTH:500px><br>
              <br>
              Algorytm składa się z następujących kroków. Jeżeli proces który żąda wejścia do sekcji krytycznej, nie posiada żetonu, zwiększa swoja liczbę porządkową, <i>RNi[i</i> <i>],</i> i wysyła <i>ŻĄDANIE(i</i> <i>,</i> <i>sn</i> <i>)</i> do wszystkich innych procesów (<i>sn</i> jest zaktualizowaną wartością <i>RNi[i</i> <i>]).<br>
              <br>
              </i>
              <p>
                Gdy proces <i>Pj</i> odbierze tę wiadomość, zmienia <i>RNj[i</i> <i>]</i> na <i>max(RNj[i</i> <i>],</i> <i>sn</i> <i>).</i> W wypadku kiedy <i>Pj</i> ma bezczynny żeton, wysyła go do procesu <i>Pi</i> pod warunkiem, że <i>RNj[i</i> <i>]=</i> <i>LN[i</i> <i>]+</i> <i>1</i> .<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Kiedy proces <i>Pi</i> otrzymuje żeton, uruchamia sekcję krytyczną.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Po ukończeniu sekcji krytycznej, proces <i>Pi</i> wykonuje niniejsze czynności. Zmienia wartość elementu tablicy żetonu <i>LN[i</i> <i>]</i> na <i>RNi[i</i> <i>].</i> Dla każdego procesu <i>Pj</i> , którego identyfikatora nie ma w kolejce żetonu, dodaje jego identyfikator do tej kolejki, jeśli spełniony jest warunek <i>RNi[j</i> <i>]=</i> <i>LN[j</i> <i>]+</i> <i>1</i> . Jeżeli kolejka żetonu nie jest pusta po powyższych aktualizacjach, to proces <i>Pi</i> usuwa identyfikator z początku kolejki i wysyła żeton do procesu oznaczonego tym identyfikatorem.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                W ten sposób, po wykonaniu sekcji krytycznej, proces nadaje priorytet innym procesom z zaległymi żądaniami sekcji krytycznej (priorytet, który przewyższa jego bieżące żądania w toku).<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Algorytm ten nie jest symetryczny, ponieważ proces zachowuje żeton nawet, jeśli sam nie żąda wejścia do sekcji krytycznej. Jest to przeciwieństwem koncepcji algorytmu symetrycznego autorstwa Ricarta i Agrawali, gdzie „żaden proces nie posiada prawa dostępu do swojej sekcji krytycznej, jeżeli nie było takiego żądania”.
              </p>
              <br>
              <br>
            </div>
            <b style=COLOR:#3d85c6><font size=3>Algorytm Raymonda - wprowadzenie</font></b><br>
            <hr size=2>
          </div>
          <br>
        </div>
        <div id=r:vz style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2457cqgmctgr_b.png" style=HEIGHT:342px;WIDTH:500px><br>
          <br>
          W algorytmie Raymonda, który bazuje na drzewie, procesy są logicznie zorganizowane w postaci skierowanego drzewa, takiego, że jego krawędzie wskazują w kierunku procesu, posiadającego żeton (korzeń drzewa). Każdy proces ma lokalną zmienną <i>posiadacz</i> , która wskazuje na sąsiedni proces w skierowanej ścieżce do korzenia. Tym sposobem zmienna <i>posiadacz</i> , definiuje w procesach strukturę logicznego drzewa procesów. Jeśli podążymy za wartościami zmiennych <i>posiadacz</i> w procesach, zobaczymy że każdy proces znajduje się na skierowanej ścieżce prowadzącej do procesu z żetonem. Wartość <i>posiadacz</i> korzenia, wskazuje na niego samego.<br>
          <br>
          <p>
            Każdy proces <i>P</i> utrzymuje kolejkę FIFO, oznaczaną jako <i>kolejka_żądań</i> , która przechowuje żądania tych sąsiednich procesów, które wysłały żądanie do procesu <i>P</i> , ale nie wysłano do nich jeszcze żetonu.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Algorytm Raymonda</font></b><br>
          <hr size=2><br>
        </div>
        <div id=au4q style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2458dt4gdbdr_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          Kiedy proces <i>Pi</i> chce wejść do sekcji krytycznej, wysyła <i>ŻĄDANIE</i> do procesu (wskazywany przez <i>posiadacza</i> ), wzdłuż skierowanej ścieżki prowadzącej do korzenia, pod warunkiem że nie posiada żetonu i jego <i>kolejka_żądań</i> jest pusta. Następnie <i>Pi</i> dodaje swoje żądanie do swojej <i>kolejki_żądań(i</i> <i>).</i> Należy zauważyć, że niepusta <i>kolejka_żądań</i> procesu oznacza, że wysłał on <i>ŻĄDANIE</i> do korzenia, które odnosi się do wpisu z początku kolejki.<br>
          <br>
          <p>
            Gdy proces <i>Pj</i> otrzyma <i>ŻĄDANIE</i> , umieszcza je w swojej kolejce i wysyła <i>ŻĄDANIE</i> wzdłuż skierowanej ścieżki do korzenia o ile nie wysłał jakiegoś innego <i>ŻĄDANIA</i> (które było następstwem otrzymanego wcześniej <i>ŻĄDANIA</i> i znalazło się w kolejce żądań).<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            W momencie gdy proces będący korzeniem drzewa (posiadacz żetonu), odbierze wiadomość z <i>ŻĄDANIEM</i> , wysyła żeton do procesu <i>Pi</i> , od którego otrzymał to <i>ŻĄDANIE</i> , a następnie zmienia zmienną <i>posiadacz</i> , tak aby wskazywała na proces <i>Pi</i>.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Kiedy proces <i>Pk</i> otrzyma żeton, usuwa wpis ze szczytu swojej <i>kolejki_żądań</i> , wysyła żeton do procesu <i>Pj</i> wskazywanego przez ten wpis oraz zmienia zmienną <i>posiadacz</i> na proces <i>Pj</i> . Jeśli w tym momencie <i>kolejka_żądań</i> jest niepusta , to proces wysyła <i>ŻĄDANIE</i> do procesu, który jest wskazany przez zmienną <i>posiadacz</i> .
          </p>
          <br>
          <br>
        </div>
        <div id=d2.o style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2459fbtvdhf3_b.png" style=HEIGHT:341px;WIDTH:500px><br>
          <br>
          Proces <i>Pi</i> wchodzi do sekcji krytycznej w chwili gdy dostaje żeton, a jego własny wpis jest na szczycie jego <i>kolejki_żądań</i> . W tym wypadku, proces <i>Pi</i> kasuje początkowy wpis ze swojej <i>kolejki_żądań</i> i wchodzi do sekcji krytycznej.<br>
          <br>
          <p>
            Po ukończeniu sekcji krytycznej proces <i>Pi</i> , jeżeli jego kolejka żądań jest niepusta, kasuje wpis z początku swojej kolejki, wysyła żeton do odpowiedniego procesu <i>Pj</i> i ustawia zmienną <i>posiadacz</i> na <i>Pj</i> . Jeśli kolejka procesu <i>Pi</i> jest wciąż niepusta, wtedy proces wysyła <i>ŻĄDANIE</i> do procesu, który jest wskazany przez zmienną <i>posiadacz</i>.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Algorytm Raymonda - przykład</font></b><br>
          <hr size=2><br>
          <div id=x9i. style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2460fvcfk2d8_b.png" style=HEIGHT:342px;WIDTH:500px><br>
            <br>
            Proces <i>P5</i> żąda żetonu. Żądanie dociera do aktualnego korzenia, którym jest proces <i>P1</i> <i>.</i> Korzeń po otrzymaniu żądania, przekazuje żeton do <i>P5</i> . Należy zauważyć, że w trakcie działanie algorytmu zmieniają się zmienne <i>posiadacz</i> , a wraz z nimi struktura drzewa.<br>
            <br>
          </div>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Zakleszczenia</font></b><br>
          <hr size=2>
        </div>
        <br>
      </div>
      <div id=o7b: style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2461ck6pj6g5_b.png" style=HEIGHT:344px;WIDTH:500px><br>
        <br>
        W systemach rozproszonych często pojawia się sytuacja, gdy dwa lub więcej procesów rywalizuje o pewne zasoby. Jeżeli zasoby w danym momencie będą niedostępne, procesy mogą być zmuszone do przejścia na jakiś czas w stan oczekiwania. Może się jednak zdarzyć, że jakiś zasób zostanie zablokowany przez pewien proces na czas z góry nieokreślony. W zaistniałej sytuacji inne procesy muszą oczekiwać na zasób, do którego nigdy nie będą miały dostępu. W tym wypadku mamy do czynienia z tzw. <b>zakleszczeniem</b> (ang. <i>deadlock</i> ).<br>
        <br>
        <p>
          Zagadnienie zakleszczenia pojawia się często w kontekście środowisk wieloprogramowych. W dalszej części wykładu skupimy się na problematyce zakleszczeń w systemach rozproszonych, a tym samym nie będziemy zajmować się pewnymi kwestiami, które wynikają ze środowisk nierozproszonych.
        </p>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Warunki konieczne zakleszczenia</font></b><br>
        <hr size=2><br>
        <div id=do:. style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2462c7cdj5hf_b.png" style=HEIGHT:342px;WIDTH:500px><br>
          <br>
          Aby wystąpiło zakleszczenie muszą być spełnione pewne warunki.<br>
          <br>
          <p>
            Po pierwsze musi występować <b>wzajemne</b> <b>wykluczanie</b> . Oznacza to, że jeśli w danej chwili zasobu używa jeden proces, to nie może z niego równocześnie korzystać inny.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Kolejnym warunkiem koniecznym do wystąpienia zakleszczenia jest istnienie procesu, który korzysta z jakiegoś zasobu, a jednocześnie sam oczekuje na przydział zasobu blokowanego przez inny proces.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Zakleszczenie warunkuje również brak możliwości <b>wywłaszczania</b> <b>zasobów</b> . Jeżeli proces blokuje zasób, tylko on może go zwolnić po zakończeniu swojej działania.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Ostatnim warunkiem, który nakłada się z dwoma poprzednimi, jest <b>czekanie</b> <b>cykliczne</b> . Polega to na tym, że istnieje ciąg procesów, z których każdy czeka na pewien zasób przetrzymywany przez kolejny proces w ciągu, a dodatkowo ostatni proces w ciągu czeka na zasoby przetrzymywane przez pierwszy proces w ciągu.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Graf przydziału zasobów</font></b><br>
          <hr size=2><br>
        </div>
        <div id=yop4 style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2463w4f4pcdd_b.png" style=HEIGHT:343px;WIDTH:500px><br>
          <br>
          Do ilustracji i analizy zakleszczeń można posłużyć się tzw. <b>grafami</b> <b>przydziału</b> <b>zasobów</b> (ang. <i>system</i> <i>resorce-allocation</i> <i>graph</i> ). Zbiór wierzchołków takiego grafu podzielony jest na dwa zbiory: zbiór procesów oraz zbiór zasobów. Łuk, który biegnie od procesu <i>Pi</i> do zasobu <i>Zj</i> oznacza że proces chce użyć tego zasobu i czeka na niego. Jeżeli natomiast łuk biegnie od zasobu <i>Zj</i> do procesu <i>Pi</i> , oznacza to, że zasób został przydzielony procesowi. Stąd też krawędzie tego typu zwaną są odpowiednio: <b>krawędzią</b> <b>zamówienia</b> (ang. <i>request</i> <i>edge</i> ) oraz <b>krawędzią</b> <b>przydziału</b> (ang. <i>assignment</i> <i>edge</i>).<br>
          <br>
          <p>
            Na podstawie grafu przydziału zasobów można wykazać, że jeżeli w grafie nie występują cykle, to w systemie reprezentowanym przez ten graf nie ma zakleszczeń. W przeciwnym wypadku może pojawić się zakleszczenie.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            W grafie przydziału zasobów na rysunku dla uproszczenia zasoby oznacza się prostokątami, a procesy kółkami. Egzemplarze zasobów rozróżnia się dodatkowo kropkami wewnątrz prostokątów (zasobów); gdy proces wysyła zamówienie na zasób, oznaczamy to krawędzią zamówienia dochodzącą do brzegu prostokąta, natomiast gdy proces otrzymuje przydział, to jest to konkretny egzemplarz zasobu i krawędź przydziału rozpoczyna się od kropki (egzemplarza zasobu).
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Strategie postępowania z zakleszczeniami</font></b><br>
          <hr size=2><br>
          <div id=a_n_ style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2464d4zhtdds_b.png" style=HEIGHT:343px;WIDTH:500px><br>
            <br>
            W przypadku zakleszczeń można postępować na kilka sposobów. Po pierwsze można zapewnić, aby do zakleszczeń nigdy nie dochodziło. Po drugie można zezwalać na zakleszczenia, ale po ich wystąpieniu usuwać je. Można też zakleszczenia zupełnie ignorować.
            <p>
              W systemach, w których pojawienie się zakleszczenia nie jest pożądane, stosuje się m.in metody <b>zapobiegania</b> <b>zakleszczeniom</b> (ang. <i>deadlock</i> <i>prevention</i> ) i <b>unikania</b> <b>zakleszczeń</b> (ang. <i>deadlock</i> <i>avoidance</i>).<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              Zapobieganie zakleszczeniom polega w uproszczeniu na tym, aby nie dopuścić do zajścia któregoś z warunków koniecznych do wystąpienia zakleszczenia. Realizuje się to najczęściej poprzez nałożenie ograniczeń na porządek w jakim przydzielane są zasoby do procesów.<br>
            </p>
            <p>
              <br>
            </p>
            <p>
              W metodach stosujących unikanie zakleszczeń, system stara się zebrać jak najwięcej informacji o zasobach z jakich będą korzystały procesy, tak aby podejmując później decyzje o przydziale zasobów mógł uniknąć zakleszczeń.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Zapobieganie zakleszczeniom w systemach rozproszonych</font></b><br>
            <hr size=2><br>
            <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-7-wyk-2.0-Slajd29 title=Sr-7-wyk-2.0-Slajd29> </a>
            <div id=h_ym style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2465fhmhkzhj_b.png" style=HEIGHT:342px;WIDTH:500px><br>
              <br>
              Wiele spośród algorytmów zapobiegania zakleszczeniom stosowanych w systemach nierozproszonych można zastosować również w środowiskach rozproszonych. Wymaga to oczywiście pewnych dodatkowych mechanizmów, jak m.in. odpowiedniego zastosowania globalnego porządku w systemie (np. wobec zasobów). Nieraz koszt takiego rozwiązania jest jednak nieopłacalny i trzeba zastosować inne rozproszone metody.
              <p>
                <br>
              </p>
              <p>
                Poniżej prezentujemy zastosowanie znaczników czasowych, jako środek służący do zapobiegania zakleszczeń w systemach z wywłaszczaniem zasobów. Aby uprościć analizę, zakładamy istnienie jednego egzemplarza każdego zasobu.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                W przedstawianym algorytmie każdy proces ma przypisany unikalny priorytet, który decyduje o tym, czy jeden proces powinien czekać na inny. Stosując informacje o priorytetach procesów, możemy nakazać, aby w razie konfliktu proces <i>Pi</i> o wyższym priorytecie mógł czekać na proces <i>Pj</i> o niższym priorytecie. W przeciwnym wypadku, gdy proces <i>Pi</i> ma niższy priorytet, usuwamy go z pamięci.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Stosując powyższy schemat pozbyliśmy się problemu zakleszczeń, ale pojawił się niestety problem w postaci możliwości zagłodzenia procesów o niskich priorytetach. Może się zdarzyć, że procesy takie będą wiecznie wywłaszczane przez procesy o wyższych priorytetach. W tym celu zaproponowano użycie znaczników czasowych i zaproponowano dwa podejścia do rozwiązania problemu. Unikalne znaczniki czasu nadaje się procesom raz, w trakcie ich utworzenia.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                W <b>pierwszej</b> metodzie, zwanej <b>czekanie</b> <b>albo</b> <b>śmierć</b> (ang. <i>wait-die</i> ), nie używa się wywłaszczeń. Gdy proces <i>Pi</i> przetrzymuje zasób, którego chce użyć inny proces <i>Pj</i> , to <i>Pj</i> może poczekać aż zasób zostanie zwolniony tylko wtedy, gdy jego znacznik czasu jest mniejszy od znacznika czasu procesu <i>Pi</i> . W przeciwnym razie proces <i>Pj</i> jest usuwany z pamięci.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                <b>Zranienie</b> <b>albo</b> <b>czekanie</b> (ang. <i>wound-wait</i> ) jest drugim zaproponowanym podejściem, które stosuje wywłaszczanie. W tym podejściu jeżeli proces <i>Pj</i> oczekuje zasobu używanego aktualnie przez <i>Pi</i> , to <i>Pj</i> może poczekać na zasób pod warunkiem, że znacznik czasu <i>Pj</i> jest większy. Inaczej <i>Pj</i> zostaje „zraniony”, czyli usunięty z pamięci.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Jak można zauważyć powyższe metody różnią się znacząco od siebie. Niemniej pozwalają na uniknięcie wcześniejszego problemu głodzenia, jeżeli usunięte procesy nie będą otrzymywały nowych znaczników.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Wadą obu schematów jest występowanie niepotrzebnych wywłaszczeń nawet, gdy nie ma zakleszczeń. W celu uniknięcia tego typu sytuacji można zastosować wykrywanie zakleszczeń.
              </p>
              <br>
              <br>
              <b style=COLOR:#3d85c6><font size=3>Wykrywanie zakleszczeń</font></b><br>
              <hr size=2><br>
              <div id=ohb2 style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2466ft5bmqcb_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                <br>
                W algorytmach <b>wykrywania</b> <b>zakleszczeń</b> , konstruuje się tzw. <b>graf</b> <b>oczekiwania</b> (ang. <i>wait-for</i> <i>graph</i> ), który jest grafem skierowanym. Łuki w takim grafie reprezentują stan przydziału zasobów. Mając graf oczekiwania i wiedząc, czy istnieje w nim cykl możemy stwierdzić, czy mamy do czynienia z zakleszczeniem.<br>
                <br>
                <p>
                  Wraz z pojęciem grafu oczekiwania w systemach rozproszonych, pojawiają się również pojęcia <b>lokalnego</b> <b>i</b> <b>globalnego</b> <b>grafu</b> <b>oczekiwania</b>.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Lokalny graf oczekiwania związany jest z danym stanowiskiem przetwarzania. Węzły w takim grafie odpowiadają procesom lokalnym lub zdalnym, które aktualnie utrzymują lub zamawiają zasoby lokalne na określonym komputerze. Zauważmy, że w ramach poszczególnych stanowisk, procesy mogą się powtarzać.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Globalny graf oczekiwania odnosi się do wszystkich stanowisk i otrzymywany jest w wyniku zsumowania lokalnych grafów oczekiwania.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Fakt, że lokalne grafy nie posiadają cykli nie oznacza, że nie występuje zakleszczenie. Może ono być widoczne dopiero w globalnym grafie. Zatem aby stwierdzić że w systemie rozproszonym występuje zakleszczenie, musimy znać globalny graf oczekiwania.<br>
                </p>
                <p>
                  <br>
                </p>
                <p>
                  Na rysunku zilustrowano przykład zakleszczenie trzech procesów <i>P2</i> , <i>P3</i> oraz <i>P4</i> .
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Podejście scentralizowane</font></b><br>
                <hr size=2><br>
                <div id=mzo2 style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2467cxrxsx3j_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                  <br>
                  Centralnym elementem podejścia scentralizowanego jest <b>koordynator</b> <b>wykrywania</b> <b>zakleszczeń</b> (ang. <i>deadlock-detection</i> <i>coordinator</i> ). Jest to pojedynczy proces, którego głównym zadaniem jest utrzymanie globalnego grafu oczekiwania poprzez sumowanie lokalnych grafów. Ze względu na charakterystykę i opóźnienia panujące w systemie rozproszonym wiedza koordynatora o globalnym grafie oczekiwania nie zawsze jest kompletna i aktualna. Dlatego wprowadzono kolejne rozróżnienie między grafami oczekiwania: <b>graf</b> <b>rzeczywisty</b> odzwierciedlający rzeczywisty stan systemu oraz <b>graf</b> <b>konstruowany</b> , czyli taki jakim widzi go koordynator. Innymi słowy graf konstruowany jest pewnym przybliżeniem grafu rzeczywistego. Aby graf konstruowany był przydatny musi dać możliwość poprawnego wykrycia zakleszczeń.<br>
                  <br>
                  <p>
                    Graf oczekiwania może być konstruowany na kilka sposobów. Informacje o globalnym grafie oczekiwania można aktualizować przy okazji każdej zmiany grafów lokalnych lub po uzbieraniu określonej liczby zmian. Istnieje także możliwość konstrukcji grafu w momencie gdy wywoływany jest algorytm wykrywania zakleszczeń.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    W wypadku zastosowaniu pierwszego schematu aktualizacji grafu, gdy usuwany lub dodawany jest jakiś łuk do któregoś z lokalnych grafów, powiadamiany jest o tym koordynator, a następnie aktualizowany jest globalny graf oczekiwania. Na podstawie tego grafu koordynator wykrywa zakleszczenia i powiadamia odpowiednie stanowiska o swojej decyzji co do usunięcia lub wstrzymania niektórych procesów.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Graf oczekiwania konstruowany według powyższego schematu nie jest wolny od pewnych niedogodności w postaci np. <b>fałszywych</b> <b>cykli</b> (ang. <i>false</i> <i>cycles</i> ). Fałszywe cykle pojawiają się na skutek niedoinformowania koordynatora o aktualnie zwolnionych i przydzielonych zasobach. W ten sposób w grafie oczekiwania istnieje czasami łuk, którego nie ma w rzeczywistym grafie oczekiwania, a który to powoduje wykrycie nieistniejącego zakleszczenia. Niepotrzebne wycofania mogą się również pojawić, gdy procesy, które wcześniej powodowały zakleszczenie, są nagle usuwane bez wiedzy koordynatora.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Kolejna wersja algorytmu scentralizowanego zakłada, że aktualizacje grafu oczekiwania następują w trakcie wywoływania algorytmu wykrywania zakleszczeń. Przewagą tego algorytmu nad poprzednim jest brak wykrywania fałszywych zakleszczeń. Gdy proces <i>Pi</i> zamawia zasób od <i>Pj</i> , a oba procesy są na różnych stanowiskach, zamówienie opatrywane jest unikalnym znacznikiem czasu <i>t</i> . Tym samym krawędź zamówienia od <i>Pi</i> do <i>Pj</i> również posiada znacznik <i>t</i> . Ponadto krawędź ta wstawiana jest tylko do lokalnego grafu na stanowisku, gdzie przebywa proces <i>Pi</i> . W przypadku drugiego stanowiska wspomniana krawędź zamówienia jest wstawiana tylko wtedy, jeżeli stanowisko to otrzymało nowe zamówienie na zasób i nie może go od razu spełnić. Lokalne zamówienia nie są opatrywane znacznikami.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    W momencie kiedy koordynator chce zbudować globalny graf oczekiwania, rozsyła do wszystkich stanowisk prośbę o dostarczenie grafów lokalnych. Po otrzymaniu wszystkich lokalnych grafów, składany jest graf globalny. Wierzchołkami globalnego grafu są wszystkie procesy w systemie, a do zbioru krawędzi trafiają te krawędzie z lokalnych grafów, które albo nie są oznaczone znacznikami czasu, albo posiadają znacznik i pojawiają się w więcej niż jednym lokalnym grafie oczekiwania. Jeżeli w tak skonstruowanym grafie występuje cykl, to w systemie jest zakleszczenie.
                  </p>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Podejście scentralizowane - przykład</font></b><br>
                  <hr size=2>
                </div>
                <br>
              </div>
              <div id=fwcq style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2468dfmjkfc7_b.png" style=HEIGHT:342px;WIDTH:500px><br>
                <br>
                W podejściu scentralizowanym koordynator wykrywania zakleszczeń zbiera od różnych stanowisk lokalne grafy oczekiwania, a następnie konstruuje globalny graf oczekiwania. Na załączonej ilustracji możemy zobaczyć u koordynatora sumę dwóch grafów lokalnych ze stanowisk 1 i 2. Przerywaną linią oznaczono strzałki, które wspólnie tworzą wykryty cykl w globalnym grafie oczekiwania, a tym samym reprezentują zakleszczenie.<br>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Podejście rozproszone</font></b><br>
                <hr size=2><br>
                <div id=cxa5 style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2469z7h5494k_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                  <br>
                  W przeciwieństwie do algorytmu scentralizowanego w podejściu rozproszonym konstrukcją globalnego grafu oczekiwania, a dokładniej jego części, zajmuje się wiele procesów. Odpowiedzialność za wykrywanie zakleszczeń jest więc podzielona pomiędzy tych kilka procesów. Jeżeli, któryś z takich procesów wykryje cykl w swojej części globalnego grafu, oznacza to, że wystąpiło zakleszczenie.<br>
                  <br>
                  <p>
                    Graf lokalny każdego procesu różni się nieco od tego w algorytmie scentralizowanym, gdyż dodano do niego specjalny wierzchołek <i>Pzew</i> . Jeżeli istnieje łuk z pewnego procesu <i>Pi</i> do <i>Pzew</i> , to <i>Pi</i> czeka na zasób z innego stanowiska przetrzymywany przez dowolny proces. Jeżeli zachodzi sytuacja odwrotna tzn. pojawia się łuk od <i>Pzew</i> do <i>Pi</i> , znaczy to, że jakiś zdalny proces czeka na zasoby, do których dostęp ma w danej chwili lokalny proces.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Schemat działania algorytmu wygląda następująco. Jeżeli stanowisko wykryło w swoim grafie oczekiwania cykl, który nie zawiera <i>Pzew</i> , to w systemie jest zakleszczenie. Jeżeli cykl zawiera wierzchołek <i>Pzew</i> , to wykonywany jest algorytm rozproszony.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Jeżeli stanowisko <i>Si</i> wykryło cykl w grafie z wierzchołkiem <i>Pzew</i> , wysyła informacje o wystąpieniu zakleszczenia oraz dane o cyklu do stanowiska <i>Sj</i> , na którym znajduje się proces przetrzymujący aktualnie zasoby potrzebne procesowi czekającemu na <i>Pzew</i> . Stanowisko <i>Sj</i> po otrzymaniu informacji o wykryciu zakleszczenia, aktualizuje swój graf oczekiwania i szuka cyklu nie zawierającego <i>Pzew</i> . Jeżeli znajdzie, to jest zakleszczenie. Jeżeli w cyklu występuje natomiast <i>Pzew</i> , to informacje o wykryciu zakleszczenie wędrują do kolejnego stanowiska. Cała procedura powtarzana jest skończoną liczbę razy do momentu zakończenia algorytmu lub wykrycia zakleszczenia.<br>
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Do algorytmu wprowadzono pewną optymalizację komunikacji, tak aby w sytuacji, gdy kilka procesów wykryje zakleszczenie, nie wszystkie wysyłały o nim informację. Każdy proces oznaczono unikalnym identyfikatorem. Gdy stanowisko wykryje cykl, na który składa się ciąg procesów <i>(</i> <i>Pzew</i> <i>,</i> <i>P1</i> <i>,</i> <i>P2</i> <i>,</i> <i>…,</i> <i>PN</i> <i>,</i> <i>Pzew</i> <i>),</i> sprawdza czy zachodzi warunek <i>identyfikator(PN</i> <i>)</i> <i>&lt;</i> <i>identyfikator(P1</i> <i>).</i> Jeżeli warunek jest spełniony, informacja o zakleszczeniu jest wysyłana, w przeciwnym wypadku inicjatywę musi przejąć inne stanowisko.
                  </p>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Podejście rozproszone - przykład</font></b><br>
                  <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-7-wyk-2.0-Slajd34 title=Sr-7-wyk-2.0-Slajd34> </a><br>
                </div>
                <div id=n5yk style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2470dhf56fg2_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                  <br>
                  Na ilustracji przedstawiono przykładowy schemat działania rozproszonego algorytmu wykrywania zakleszczeń. Załóżmy, że stanowisko 1. wykryło cykl w swoim grafie oczekiwania <i>Pzew</i> <i>?</i> <i>P2</i> <i>?</i> <i>P1</i> <i>?</i> <i>Pzew</i>. Cykl ten zawiera wierzchołek <i>Pzew</i> połączony z procesami <i>P1</i> oraz <i>P2</i> , co oznacza, że <i>P1</i> oczekuje na zasoby przetrzymywane przez jakiś zdalny proces, natomiast <i>P2</i> używa zasobów, których żąda również zdalny proces. Ponieważ stanowisko 2. zawiera proces <i>P1</i> , który to na stanowisku 1. oczekuje na zwolnienie zasobów, graf ze stanowiska 1. przesyłany jest do stanowiska 2. Na stanowisku 2. lokalny graf oczekiwania sumowany jest z grafem otrzymanym ze stanowiska 1. W wyniku operacji sumowania okazało się, że uzyskany graf oczekiwania zawiera cykl <i>P1</i> <i>?</i> <i>P5</i> <i>?</i> <i>P2</i> <i>?</i> <i>P1</i> , czyli zostało wykryte zakleszczenie.<br>
                  <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-7-wyk-2.0-Slajd35 title=Sr-7-wyk-2.0-Slajd35> </a><br>
                </div>
              </div>
            </div>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>
<br></body>
</html>